Party

Memory limit: 256 MB

Jane has decided to hold a party for her classmates. Unfortunately, not everyone in the class likes each other. Even though the majority of pairs of the pupils from the class like each other, some of them are vicious enemies. Jane herself is a very kind person: she likes all her classmates a lot. She knows that if she invites both Larry and Mark, the boys will beat up and the party will be an unpleasant experience for everyone. Now if she does not invite Mark, but she invites Bill who is friends with Mark, then probably Mark will learn about the party from his friend and will always feel regret to her for not being invited. What a mess!

Jane's problem is the following: she would not like to invite any two classmates who are enemies, but also she has to invite every friend of every invited person. Additionally Jane would like to invite as many classmates as possible. Please help her find out what is the maximum number of guests at the party and, moreover, the number of ways this maximum can be achieved.

Input

The first line of input contains three integers , and (, , ) that denote the number of children in Jane's class, the number of pairs of friends and the number of pairs of enemies in the class respectively. For simplicity the classmates are numbered 1 through (this excludes Jane). Each of the following lines contains two integers and (, ) that represent a friendship relation between classmates and . Each of the following lines contains two integers and (, ) which mean that and are enemies. No (unordered) pair of classmates repeats in the input.

Output

The first and only line of output should hold two integers: the maximum number of guests that Jane can invite to the party and the number of ways in which this number of guests can be selected.

Example

For the input data:

6 10 2
1 2
1 3
4 1
1 5
2 5
3 2
2 4
3 4
3 5
5 4
2 6
5 6

the correct result is:

5 1

Task author: Adam Karczmarz.